`
https://leetcode.cn/problems/palindrome-partitioning/
`

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const res = []
  const track = []

  function backtrack(start) {
    // 即整个 s 被成功分割为若干个回文子串，记下答案
    if (start === s.length) {
      res.push(track.slice())
      return
    }

    for (let i = start; i < s.length; i++) {
      if (!isPalindrome(s, start, i)) {
        // s[start..i] 不是回文串，不能分割
        continue
      }
      // s[start..i] 是一个回文串，可以进行分割
      // 做选择，把 s[start..i] 放入路径列表中
      track.push(s.substring(start, i + 1));
      // 进入回溯树的下一层，继续切分 s[i+1..]
      backtrack(i + 1);
      // 撤销选择
      track.pop();
    }
  }

  backtrack(0)
  return res
};

// 用双指针技巧判断 s[lo..hi] 是否是一个回文串
function isPalindrome(s, lo, hi) {
  while (lo < hi) {
    if (s[lo] !== s[hi]) {
      return false;
    }
    lo++;
    hi--;
  }
  return true;
};